Ваша миссия 🎯
Восстановите связь между $N$ планетами, заданными как координаты в 2D-пространстве, с минимальной стоимостью сети «Гипер-туннелей».
- Цель: Подключите все $N$ планет (вершины), чтобы они были доступны (непосредственно или косвенно).
- Задача: Найдите проект сети, который минимизирует **общую стоимость**.
Анализ 🛰️
Стоимость туннеля (ребра) — это евклидово расстояние:
$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$
- Туннель можно проложить между любыми двумя планетами.
- Это означает, что у нас есть полный (плотный) граф.
Решение ⚙️
Это классическая задача минимального остовного дерева (MST) задача.
- Алгоритм: Подсказка рекомендует алгоритм Прима (вариант $O(V^2)$), идеально подходящий для плотных графов.
- Точка старта: Мы начнём наш алгоритм с планеты 0 для получения согласованного результата.
Полный граф (слева) содержит все возможные рёбра. MST (справа) — это самое дешёвое подмножество рёбер, соединяющее все вершины.